import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2025-03-09
 * Time: 20:31
 */
class Solution1 {
    public  List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();

        Arrays.sort(nums);

        int n = nums.length;
        for (int i = 0; i < n;) {
            int left = i+1, right = n-1, target = -nums[i];
            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum > target) right--;
                else if(sum < target) left++;
                else{
                    ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                    right--;left++;
                    while(left < right && nums[left] == nums[left-1]) left++;
                    while(left < right && nums[right] == nums[right+1]) right--;
                }
            }
            i++;
            while(i < n && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }
}

public class demo1 {
    public static void main(String[] args) {
        int[] n = {-4,-4,-1,0,0,0,1,1,4,4,5,6};
        Solution1 solution1 = new Solution1();
        solution1.threeSum(n);
    }
}
